//Given an integer array nums and two integers lower and upper, return the numbe
//r of range sums that lie in [lower, upper] inclusive. 
//
// Range sum S(i, j) is defined as the sum of the elements in nums between indic
//es i and j inclusive, where i <= j. 
//
// 
// Example 1: 
//
// 
//Input: nums = [-2,5,-1], lower = -2, upper = 2
//Output: 3
//Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respectiv
//e sums are: -2, -1, 2.
// 
//
// Example 2: 
//
// 
//Input: nums = [0], lower = 0, upper = 0
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 105 
// -231 <= nums[i] <= 231 - 1 
// -105 <= lower <= upper <= 105 
// The answer is guaranteed to fit in a 32-bit integer. 
// 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 
// 👍 392 👎 0


package leetcode.editor.cn;

//Java：Count of Range Sum
public class P327CountOfRangeSum {
    public static void main(String[] args) {
        Solution solution = new P327CountOfRangeSum().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            long s = 0;
            long[] sum = new long[nums.length + 1];
            for (int i = 0; i < nums.length; ++i) {
                s += nums[i];
                sum[i + 1] = s;
            }
            return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
        }

        public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
            if (left == right) {
                return 0;
            } else {
                int mid = (left + right) / 2;
                int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
                int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
                int ret = n1 + n2;

                // 首先统计下标对的数量
                int i = left;
                int l = mid + 1;
                int r = mid + 1;
                while (i <= mid) {
                    while (l <= right && sum[l] - sum[i] < lower) {
                        l++;
                    }
                    while (r <= right && sum[r] - sum[i] <= upper) {
                        r++;
                    }
                    ret += r - l;
                    i++;
                }
                // 随后合并两个排序数组
                long[] sorted = new long[right - left + 1];
                int p1 = left, p2 = mid + 1;
                int p = 0;
                while (p1 <= mid || p2 <= right) {
                    if (p1 > mid) {
                        sorted[p++] = sum[p2++];
                    } else if (p2 > right) {
                        sorted[p++] = sum[p1++];
                    } else {
                        if (sum[p1] < sum[p2]) {
                            sorted[p++] = sum[p1++];
                        } else {
                            sorted[p++] = sum[p2++];
                        }
                    }
                }
                for (int j = 0; j < sorted.length; j++) {
                    sum[left + j] = sorted[j];
                }
                return ret;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}